/**
 * 这是 LeetCode 第 3. 无重复字符的最长子串 的解决方案
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters
 */
import java.util.HashMap;
import java.util.Map;

class LongestSubstringWithoutRepeatingCharacters{
    
    /**
     * 方法： lengthOfLongestSubstring
     * 逻辑: 使用滑动窗口和哈希表来记录字符的最新位置，从而找到最长的无重复字符子串。
     * Args: s - 输入的字符串
     * Returns: 最长无重复字符子串的长度
     * Time: O(n) - 每个字符最多被访问两次
     * Space: O(1) ： 字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1) 大小的额外空间。
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, left = -1, len = s.length();
        for (int right = 0; right < len; right++){
            Character ch = s.charAt(right);
            if (map.containsKey(ch)){
                left = Math.max(left, map.get(ch));
            }
            map.put(ch, right);
            res = Math.max(res, right - left);
        }
        return res;
    }

    /**
     * 方法： lengthOfLongestSubstring1
     * 逻辑: 动态规划 + 哈希表。
     * Args: s - 输入的字符串
     * Returns: 最长无重复字符子串的长度
     * Time: O(n) - 其中 N 为字符串长度，动态规划需遍历计算 dp 列表
     * Space: O(1) ： 字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1) 大小的额外空间。
     */
    public int lengthOfLongestSubstring1(String s){
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp =0, len = s.length();
        for(int j = 0; j< len; j++){
            int i = dic.getOrDefault(s.charAt(j), -1); //获取所以i
            dic.put(s.charAt(j), j);//更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp);// max(dp[j - 1], dp[j])
        }
        return res;
    }

    /**
     * 方法： lengthOfLongestSubstring2
     * 逻辑: 使用滑动窗口和布尔数组来记录字符是否在当前窗口内，从而找到最长的无重复字符子串。
     * Args: s - 输入的字符串
     * Returns: 最长无重复字符子串的长度
     * Time: O(n) - 每个字符最多被访问两次
     * Space: O(1) - 布尔数组的大小固定为128
     */
    public int lengthOfLongestSubstring2(String s) {
        char[] ch = s.toCharArray();
        int n = s.length(), ans = 0, left = 0;
        boolean[] has = new boolean[128]; // 也可以用 HashSet<Character>，这里为了效率用的数组
        for (int right = 0; right < n; right++){
            char c = ch[right];
            // 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
            // 所以要在加入 c 之前，先移出窗口内的 c
            while (has[c]) { // 窗口内有 c
                has[ch[left++]] = false;
            }
            has[c] = true;
            ans = Math.max(ans, right-left+1);
        }
        return ans;
    }

    public static void main(String[] args){
        String s = "pwwkew";
        LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters();
        System.out.println(l.lengthOfLongestSubstring1(s));
    }
}